#include <stdio.h>   // 提供输入输出函数，如 printf、scanf
#include <stdlib.h>  // 提供动态内存分配函数，如 malloc、free

#define MAX_SIZE 1000 // 定义最大节点数量，限制优先队列的容量

// 哈夫曼树节点结构体定义
typedef struct Node {
    int value;           // 节点存储的权值
    struct Node *left;   // 指向左子节点的指针
    struct Node *right;  // 指向右子节点的指针
    int height;          // 节点的高度，用于处理权值相同的情况
} Node;

// 优先队列结构体定义
typedef struct {
    Node *data[MAX_SIZE];  // 存储队列元素的数组
    int size;              // 队列当前元素个数
} PriorityQueue;

// step 1# 初始化优先队列
void initPriorityQueue(PriorityQueue *pq) {
    pq->size = 0; // 设置初始大小为0
}

// step 2# 创建新节点
Node *createNode(int value) {
    Node *node = (Node *)malloc(sizeof(Node)); // 分配内存
    node->value = value;      // 赋值权重
    node->left = NULL;        // 左子节点为空
    node->right = NULL;       // 右子节点为空
    node->height = 0;         // 初始高度为0
    return node;              // 返回新节点
}

// step 3# 向优先队列添加元素，维持最小堆性质
void push(PriorityQueue *pq, Node *node) {
    int i = pq->size++; // 插入新元素的位置
    while (i > 0) {
        int parent = (i - 1) / 2; // 计算父节点位置
        if (pq->data[parent]->value < node->value ||
            (pq->data[parent]->value == node->value && pq->data[parent]->height <= node->height)) {
            break; // 满足堆性质，不需要上浮
        }
        pq->data[i] = pq->data[parent]; // 上浮父节点
        i = parent;
    }
    pq->data[i] = node; // 插入新节点
}

// step 4# 从优先队列中弹出最小元素
Node *pop(PriorityQueue *pq) {
    Node *min = pq->data[0];           // 最小元素在队首
    Node *last = pq->data[--pq->size]; // 取出队尾元素
    int i = 0;
    while (i * 2 + 1 < pq->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int smallest = left;
        // 比较左右子节点，选出较小的
        if (right < pq->size && (pq->data[right]->value < pq->data[left]->value ||
                                 (pq->data[right]->value == pq->data[left]->value && pq->data[right]->height < pq->data[left]->height))) {
            smallest = right;
        }
        // 如果last已经比子节点小，则不需下沉
        if (last->value < pq->data[smallest]->value ||
            (last->value == pq->data[smallest]->value && last->height <= pq->data[smallest]->height)) {
            break;
        }
        pq->data[i] = pq->data[smallest]; // 下沉较小子节点
        i = smallest;
    }
    pq->data[i] = last; // 放置last节点
    return min;         // 返回原队首元素
}

// step 5# 构建哈夫曼树
Node *buildHuffmanTree(int values[], int n) {
    PriorityQueue pq;
    initPriorityQueue(&pq); // 初始化优先队列

    // 将所有权值转换为单节点并加入队列
    for (int i = 0; i < n; i++) {
        push(&pq, createNode(values[i])); // 创建并插入新节点
    }

    // 构建哈夫曼树
    while (pq.size > 1) {
        Node *left = pop(&pq);   // 弹出最小节点
        Node *right = pop(&pq);  // 弹出次小节点
        Node *parent = createNode(left->value + right->value); // 创建新父节点

        // 保证左子树权值不大于右子树，或高度不高于右子树
        if (left->value > right->value || (left->value == right->value && left->height > right->height)) {
            Node *temp = left;
            left = right;
            right = temp;
        }

        parent->left = left;   // 连接左子节点
        parent->right = right; // 连接右子节点
        parent->height = (left->height > right->height ? left->height : right->height) + 1; // 更新高度

        push(&pq, parent); // 将合并后节点重新加入队列
    }

    return pop(&pq); // 返回最终根节点
}

// step 6# 中序遍历哈夫曼树
void inorderTraversal(Node *root) {
    if (root != NULL) {
        inorderTraversal(root->left);       // 递归遍历左子树
        printf("%d ", root->value);         // 输出当前节点值
        inorderTraversal(root->right);      // 递归遍历右子树
    }
}

// step 7# 主函数入口
int main() {
    int n, values[MAX_SIZE];
    scanf("%d", &n); // 读取输入个数
    for (int i = 0; i < n; i++) {
        scanf("%d", &values[i]); // 读取各权值
    }

    Node *root = buildHuffman*
